package earliestFullBloom;

import java.util.*;

public class Solution {
    public class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }
    public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }
    class Node {
        public int val;
        public List<Node> children;

        public Node() {}

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, List<Node> _children) {
            val = _val;
            children = _children;
        }
    };
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        while (root!=null || !stack.isEmpty()) {
            while (root!=null) {
                list.add(root.val);
                stack.push(root);
                root = root.left;
            }
            root = stack.pop().right;
        }
        return list;
    }
    public List<Integer> postorderTraversal(TreeNode root) {
        // 左子树 右子树 值
        Stack<TreeNode> stack = new Stack<>();
        List<Integer> list = new ArrayList<>();
        TreeNode pre = null;
        while (root!=null||!stack.isEmpty()) {
            while (root!=null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            if(root.right == null || root.right==pre) {
                list.add(root.val);
                pre = root;
                root = null;
            } else {
                stack.push(root);
                root = root.right;
            }
        }
        return list;
    }
    class MyStack {
        Queue<Integer> queue1 = new ArrayDeque<>();
        Queue<Integer> queue2 = new ArrayDeque<>();
        public MyStack() {

        }

        public void push(int x) {
            queue2.offer(x);
            while (!queue1.isEmpty()) {
                queue2.add(queue1.poll());
            }
            Queue<Integer> tmp = queue1;
            queue1 = queue2;
            queue2 = tmp;
        }

        public int pop() {
            return queue1.poll();
        }

        public int top() {
            return queue1.peek();
        }

        public boolean empty() {
            return queue1.isEmpty();
        }
    }
    class MyQueue {
        // 栈来实现队列
        Stack<Integer> stack = new Stack<>();
        public MyQueue() {

        }

        public void push(int x) {
            // 放入栈底
            Stack<Integer> tmp = new Stack<>();
            while (!stack.isEmpty()) {
                tmp.push(stack.pop());
            }
            stack.push(x);
            while (!tmp.isEmpty()) {
                stack.push(tmp.pop());
            }
        }

        public int pop() {
            return stack.pop();
        }

        public int peek() {
            return stack.peek();
        }

        public boolean empty() {
            return stack.isEmpty();
        }
    }
    public boolean isPalindrome(ListNode head) {
        Stack<Integer> stack = new Stack<>();
        ListNode p = head;
        while (p!=null) {
            stack.push(p.val);
            p = p.next;
        }
        p = head;
        int n = stack.size();
        while (stack.size()>n/2) {
            if(stack.pop()!=p.val) {
                return false;
            }
            p = p.next;
        }
        return true;
    }
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        // 下一个更大的元素
        Map<Integer,Integer> map = help(nums2);
        int[] ans = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) {
            ans[i] = map.getOrDefault(nums1[i],-1);
        }
        return ans;
    }
    private Map<Integer,Integer> help(int[] nums) {
        Map<Integer,Integer> map = new HashMap<>();
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < nums.length; i++) {
            while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
                map.put(nums[stack.pop()],nums[i]);
            }
            stack.push(i);
        }
        return map;
    }
    public List<Integer> preorder(Node root) {
        Stack<Node> stack = new Stack<>();
        List<Integer> ans = new ArrayList<>();
        if(root==null)return ans;
        stack.push(root);
        while (!stack.isEmpty()) {
            Node p = stack.pop();
            ans.add(p.val);
            for (int i = p.children.size()-1; i >= 0; i--) {
                stack.push(p.children.get(i));
            }
        }
        return ans;
    }
    public List<Integer> postorder(Node root) {
        //
        List<Integer> ans = new ArrayList<>();
        if(root == null)return ans;
        Set<Node> visited = new HashSet<>();
        Stack<Node> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            Node p = stack.peek();
            if(p.children.size() == 0|| visited.contains(p)) {
                ans.add(p.val);
                stack.pop();
            } else {
                for (int i = p.children.size()-1; i >= 0; i--) {
                    stack.push(p.children.get(i));
                }
                visited.add(p);
            }
        }
        return ans;
    }
    public int calPoints(String[] operations) {
        Stack<Integer> stack = new Stack<>();
        for (String op: operations) {
            if(op.equals("+")){
                int pre1 = stack.pop();
                int pre2 = stack.pop();
                stack.push(pre2);
                stack.push(pre1);
                stack.push(pre1+pre2);
            } else if (op.equals("D")){
                stack.push(stack.peek()*2);
            } else if(op.equals("C")){
                stack.pop();
            } else {
                stack.push(Integer.parseInt(op));
            }
        }
        int ans = 0;
        while (!stack.isEmpty()) {
            ans+=stack.pop();
        }
        return ans;
    }

    TreeNode ans;
    TreeNode p;
    public TreeNode increasingBST(TreeNode root) {
        //
        ans = new TreeNode();
        p = ans;
        inorder(root);
        return ans.right;
    }
    public void inorder(TreeNode node) {
        if(node == null) {
            p.right = null;
            return;
        }
        inorder(node.left);
        p.right = node;
        p = p.right;
        node.left = null;
        inorder(node.right);
    }
    public String removeOuterParentheses(String s) {
        //
        Stack<Character> stack = new Stack<>();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            if(s.charAt(i) == '(') {
                if(!stack.isEmpty()) {
                    sb.append('(');
                }
                stack.push('(');
            } else {
                // 是不是最外层的括号
                if(stack.size() > 1) {
                    sb.append('(');
                }
                stack.pop();
            }
        }
        return sb.toString();
    }
    public String removeDuplicates(String s) {
        //
        Stack<Character> stack = new Stack<>();
        for (char c: s.toCharArray()) {
            if(!stack.isEmpty()&&c == stack.peek()) {
                stack.pop();
            } else {
                stack.push(c);
            }
        }
        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()) {
            sb.append(stack.pop());
        }
        return sb.reverse().toString();
    }
    public int[] finalPrices(int[] prices) {
        //
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < prices.length; i++) {
            while (!stack.isEmpty() && prices[stack.peek()] >= prices[i]) {
                prices[stack.peek()]-=prices[i];
            }
            stack.push(i);
        }
        return prices;
    }
    public String makeGood(String s) {
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if(Math.abs(c - stack.peek()) == 'a'-'A') {
                stack.pop();
            } else {
                stack.push(c);
            }
        }
        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()) {
            sb.append(stack.pop());
        }
        return sb.reverse().toString();
    }
    public int minOperations(String[] logs) {
        Stack<String> stack = new Stack<>();
        for (String log: logs) {
            if(log.equals("../")) {
                if(!stack.isEmpty())stack.pop();
            } else if(log.equals("./")){

            } else {
                stack.push(log);
            }
        }
        return stack.size();
    }
    public long maximumTripletValue(int[] nums) {
        // dp 动态规划
        // (nums[i]-nums[j])*nums[k]  i最大
        // k最大
        // pre[i] 表示在i之前的最大值 包括i
        // back[k] 表示在k之后的最大值 包括k
        int n = nums.length;
        int[] pre = new int[n];
        int[] back = new int[n];
        pre[0] = nums[0];
        back[n-1] = nums[n-1];
        for (int i = 1; i < n; i++) {
            pre[i] = Math.max(pre[i-1],nums[i]);
        }
        for (int i = n-2; i >=0 ; i--) {
            back[i] = Math.max(back[i+1],nums[i]);
        }
//        System.out.println(Arrays.toString(pre));
//        System.out.println(Arrays.toString(back));
        long ans = 0;
        for (int j = 1; j < n-1; j++) {
            ans = Math.max(ans,((long)pre[j-1]-nums[j])*back[j+1]);
        }
        return ans;
    }
    public int minSizeSubarray(int[] nums, int target) {
        int sum = Arrays.stream(nums).sum();
        int t = (target/ sum);
        int m = target%sum;
        // 看剩下的环形数组里有无和 == m
        int l = 0,r = 0;
        int[] tmp = new int[nums.length*2];
        for (int i = 0; i < nums.length; i++) {
            tmp[i] = nums[i];
        }
        for (int i = 0; i < nums.length; i++) {
            tmp[i+nums.length] = nums[i];
        }
        // System.out.println(Arrays.toString(tmp));
        int minLen = -1;
        int cur = nums[0];
        while (l<tmp.length&&r<tmp.length) {
            if(cur > m) {
                cur-=tmp[l];
                l++;
            } else if (cur<m) {
                r++;
                if(r>=tmp.length)break;
                cur+=tmp[r];
            } else {
                if(minLen == -1) {
                    minLen = (r-l+1);
                } else {
                    minLen = Math.min(minLen,(r-l)+1);
                }
                cur-=tmp[l];
                l++;
            }
        }
        if(minLen == -1) return -1;
        return t*nums.length+minLen;
    }
    public int maxProfit(int[] prices) {
        int min = prices[0];
        int ans = 0;
        for (int i = 1; i < prices.length; i++) {
            ans = Math.max(ans,prices[i]-min);
            min = Math.min(min,prices[i]);
        }
        return ans;
    }
//    public List<Integer> postorder(Node root) {
//        List<Integer> list = new ArrayList<>();
//        dfs(root,list);
//        return list;
//    }
//    private void dfs(Node root,List<Integer> list) {
//        if(root == null) return;
//        for (Node c: root.children) {
//            dfs(c,list);
//        }
//        list.add(root.val);
//    }
//    public List<Integer> preorder(Node root) {
//        List<Integer> list = new ArrayList<>();
//        dfs(root,list);
//        return list;
//    }
//    private void dfs(Node root,List<Integer> list) {
//        if(root == null) return;
//        list.add(root.val);
//        for (Node c: root.children) {
//            dfs(c,list);
//        }
//    }
//    public int earliestFullBloom(int[] plantTime, int[] growTime) {
//
//    }
}
